Routing optimization may aim to identify a routing solution with optimal cost from a finite set of candidates. The classic traveling salesman problem (TSP) and vehicle routing problem (VRP) are some examples of variants to the routing optimization problem. Real-world applications of routing optimization may be found in areas such as telecommunications network design, task scheduling, transportation system planning, energy, finance, and supply chain. Routing optimization problems involving finding efficient routes for vehicles are commonly referred to as vehicle routing problems (VRP). There are several variants of VRP, such as VRP with pickup and delivery (VRPPD), VRP with Last-In-First-Out, VRP with Time Windows (VRPTW), and Capacitated VRP.
In a typical routing optimization situation, one or more optimal routes (e.g., shortest-distance routes) that pass through each of N given locations need to be identified. It has been challenging to identify the optimal routes because even for a small value of N, the total number of candidate routes is exceedingly large. It has been well-established that determining the optimal solution to VRP is NP-hard. In practice, it is often impossible to test every possible candidate route through trial and error due to constraints on resources, time, etc. Thus, it is desirable to provide a method for determining routing with a shorter time and a greater accuracy.